/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

import java.util.ArrayList;
import java.util.List;
/**
 * <p>标题：单词拆分</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/word-break/
 * </pre>
 * <p>创建日期：2019年11月27日上午9:35:10</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code139WordBreak</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code139WordBreak
{
	public static void main(String[] args)
	{
		/**
		 * 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

		说明：

		拆分时可以重复使用字典中的单词。
		你可以假设字典中没有重复的单词。
		示例 1：

		输入: s = "leetcode", wordDict = ["leet", "code"]
		输出: true
		解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
		示例 2：

		输入: s = "applepenapple", wordDict = ["apple", "pen"]
		输出: true
		解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
		     注意你可以重复使用字典中的单词。
		示例 3：

		输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
		输出: false

		 */
		//		String s = "catsandog";
		//		List<String> wordDict = new ArrayList<String>();
		//		wordDict.add("cats");
		//		wordDict.add("dog");
		//		wordDict.add("sand");
		//		wordDict.add("and");
		//		wordDict.add("cat");
		//		String s = "applepenapple";
		//		List<String> wordDict = new ArrayList<String>();
		//		wordDict.add("apple");
		//		wordDict.add("pen");
		String s = "leetcode";
		List<String> wordDict = new ArrayList<String>();
		wordDict.add("leet");
		wordDict.add("code");
		boolean wordBreak = wordBreak(s, wordDict);
		System.out.println(wordBreak);
	}

	/**
	 * 本题采用动态规划思路:
	 * 		记字符串S,S(i,j)表示截取位置i到j的字符串，不包含j
	 * 		记字典wordDict,wordDict(s)表示字典包含字符串s
	 * 		记dp[i]表示到字符串位置i,不包含i,可以拆分的情况
	 * 		若dp[i]=true 即到字符串i处，可以拆分出包含在wordDict里的字符串
	 * 		则有：
	 * 			dp[i]=dp[j] && wordDict(S(j,i)),	j<i
	 * 		考虑各种情况:
	 * 			dp[i]:{
	 * 					true,	即wordDict(S)
	 * 					true,	dp[0]=true,即字符串S为空
	 * 					dp[j] && wordDict(S(j,i)),	j<i
	 * 				}
	 * 		由于dp[0]表示空字符串的情况,因此dp的长度为S.length()+1
	 * 
	 * 
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(n)
	 * 
	 * @param s
	 * @param wordDict
	 * @return
	 */
	public static boolean wordBreak(String s, List<String> wordDict)
	{
		//1.字符串整个在字典中，直接返回true
		if (wordDict.contains(s))
		{
			return true;
		}
		//2.初始化长度为s.length()+1的dp数组
		boolean[] dp = new boolean[s.length() + 1];
		//3.初始化字符串为空的情况
		dp[0] = true;
		//4.外层循环字符串的长度
		for (int i = 1; i < dp.length; i++)
		{
			//5.内层循环控制每次拆分的起点
			for (int j = 0; j < i; j++)
			{
				/**
				 * 6.判断起点j到字符串长度端点i所截取的字符串是否在字典中，
				 * 而判断的前提是起点j之前的字符串拆分的字符串都包含在字典中
				 */
				if (dp[j] && wordDict.contains(s.substring(j, i)))
				{
					dp[i] = true;
					break;
				}
			}
		}
		return dp[s.length()];
	}
}
